package LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class Code226_invertTree {
    // 递归交换左右子树
    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        dfs(root);
        return root;
    }

    private void dfs(TreeNode node) {
        if (node == null){
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        dfs(node.left);
        dfs(node.right);
    }

    // 广度优先，交换左右节点
    public TreeNode invertTree2(TreeNode root) {
        if (root == null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 交换
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return root;
    }
}
